๋ฌธ์
Programmers - ์๋ฌผ์ ์ ์ด์
๐ Logic
for (int r = 0; r < M - 1 + N; r++) {
for (int c = 0; c < M - 1 + N; c++) {
for (int rotate = 0; rotate < 4; rotate++) {
// ์๋ฌผ์ ๋ฅผ ์ค์์ ๋๊ณ , ํค๋ฅผ ๋๋ ค๊ฐ๋ฉด์ ํ์ธํ ํฐ ๋ฐฐ์ด ์ ์ธ
bigMap = new int[N + (M - 1) * 2][N + (M - 1) * 2];
// ์๋ฌผ์ ๋ฅผ ์ค์์ ๋ฐฐ์น
for (int i = 0; i < N; i++)
System.arraycopy(lock[i], 0, bigMap[M - 1 + i], M - 1, N);
// bigMap์ ํค๋ฅผ ๋ํด ์๋ฌผ์ ์ ๋ง๋์ง ํ์ธํ ๊ฒ
match(key, r, c);
if (canUnlock()) return true;
}
}
}
-
์ ์ฒด ํ๋ฆ์,
- ์๋ฌผ์ ์ ํค๋ฅผ ๋ ์ ์๋ ํฐ 2์ฐจ์ ๋ฐฐ์ด์ ์ ์ธํ๊ณ ,
- ์๋ฌผ์ ๋ฅผ ์ค์์ ๋ ์ฑ๋ก, ํค๋ฅผ ๋๋ ค๊ฐ๋ฉด์ ๋ง์ถฐ๋ณด๊ณ , ์ ๊ธ ํด์ ๊ฐ ๊ฐ๋ฅํ์ง ํ์ธํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Solution {
static int M;
static int N;
static int[][] bigMap;
public boolean solution(int[][] key, int[][] lock) {
M = key.length;
N = lock.length;
for (int r = 0; r < M - 1 + N; r++) {
for (int c = 0; c < M - 1 + N; c++) {
for (int rotate = 0; rotate < 4; rotate++) {
// ์๋ฌผ์ ๋ฅผ ์ค์์ ๋๊ณ , ํค๋ฅผ ๋๋ ค๊ฐ๋ฉด์ ํ์ธํ ํฐ ๋ฐฐ์ด ์ ์ธ
bigMap = new int[N + (M - 1) * 2][N + (M - 1) * 2];
// ์๋ฌผ์ ๋ฅผ ์ค์์ ๋ฐฐ์น
for (int i = 0; i < N; i++)
System.arraycopy(lock[i], 0, bigMap[M - 1 + i], M - 1, N);
// bigMap์ ํค๋ฅผ ๋ํด ์๋ฌผ์ ์ ๋ง๋์ง ํ์ธํ ๊ฒ
match(key, r, c);
if (canUnlock()) return true;
}
}
}
return false;
}
// bigMap์ด 1๋ก๋ง ์ด๋ฃจ์ด์ง๋์ง ํ์ธ
static private boolean canUnlock() {
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (bigMap[M - 1 + i][M - 1 + j] != 1) return false;
return true;
}
// ํค์ ์๋ฌผ์ ๋ฅผ ๋ํ๋ ํจ์
static private void match(int[][] key, int r, int c) {
key = rotatingKey(key);
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++)
bigMap[i + r][j + c] += key[i][j];
}
// ํค๋ฅผ ์๊ณ๋ฐฉํฅ์ผ๋ก 90๋ ๋๋ฆฌ๋ ํจ์
static private int[][] rotatingKey(int[][] key) {
for (int i = 0; i < M / 2; i++) {
int[] tmp = Arrays.copyOf(key[M - i - 1], M);
key[M - i - 1] = key[i];
key[i] = tmp;
}
for (int i = 0; i < M; i++) {
for (int j = i; j < M; j++) {
int temp = key[i][j];
key[i][j] = key[j][i];
key[j][i] = temp;
}
}
return key;
}
}
โ๏ธ Review
- ์ด๋ฒ ์ฃผ์ฐจ ๋ฌธ์ ์ค์์ ์ ์ผ ์ด๋ ค์ ๋ ๋ฌธ์
-
๊ตฌํ์ด ๊น๋ํ๊ฒ ์ด๋ค์ง์ง ์์ ํ์ด ์์์ ๋ณด๋, ์๋์ ๊ฐ์ ์ ๊ธฐํ ํ์ด๋ฅผ ๋ณผ ์ ์์๋ค.
- ํค๋ฅผ ๋๋ฆฌ์ง ์๊ณ ์ธ๋ฑ์ค ์ ๊ทผ์ผ๋ก ๊ตฌํ
- ์๋ฌผ์ ๋ฅผ ์ค์์ ๋๊ณ , ํค๋ฅผ ์ฌ๋ฌ ๋ฐฉ๋ฉด์์ ๋ํด๋ณผ ์ ์๋ ํฐ ๋ฐฐ์ด ์ ์ธ
- ์ด๋ฐ ๊ตฌํ ๋ฌธ์ ๋ ๋จธ๋ฆฌ๋ฅผ ์ข ์ ๊ตด๋ฆด ์ค ์์์ผ ํ ๊ฒ ๊ฐ๋ค...